package com.shawn.algorithm.back;

/**
 * 8皇后
 */
public class EightQueen {

	private int[] result = new int[8];

	private int count = 0;

	public void cal8Queen(int row) {
		if (row >= result.length) {
			printQueens();
			count ++;
			return;
		}
		// 每一行有8种方法
		for (int column = 0; column < result.length; column++) {
			if (check(row, column)) {
				result[row] = column;
				cal8Queen(row + 1);
			}
		}
	}

	private boolean check(int row, int column) {
		int leftUp = column - 1;
		int rightUp = column + 1;
		for (int i = row - 1; i >= 0; i--) {
			if (result[i] == column) {
				return false;
			}
			if (leftUp >= 0) {
				if (result[i] == leftUp) {
					return false;
				}
			}
			if (rightUp < 8) {
				if (result[i] == rightUp) {
					return false;
				}
			}
			--leftUp;
			++rightUp;
		}
		return true;
	}

	private void printQueens() {
		for (int i = 0; i < result.length; i++) {
			for (int j = 0; j < result.length; j++) {
				if (result[i] == j) {
					System.out.print("Q	");
				} else {
					System.out.print("*	");
				}
			}
			System.out.println();
		}
		System.out.println();
	}

	public static void main(String[] args) {
		EightQueen queen = new EightQueen();
		queen.cal8Queen(0);
		System.out.println(queen.count);
	}
}
